﻿//输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。
//在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
//平衡二叉树（Balanced Binary Tree），具有以下性质：
//它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
//注：我们约定空树是平衡二叉树。

//输入描述：
//输入一棵二叉树的根节点
//返回值描述：
//输出一个布尔类型的值
//
//输入：{ 1,2,3,4,5,6,7 }
//返回值：true
//
//输入：{}
//返回值：true

/**
 * struct TreeNode {
 * int val;
 * struct TreeNode *left;
 * struct TreeNode *right;
 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        return dfs(pRoot) != -1;
    }
    int dfs(TreeNode*
        root) { // 返回值不是 -1 的话，其余的返回值表⽰的是树⾼
        if (root == nullptr) return 0;
        int left = dfs(root->left);
        if (left == -1) return -1; // 剪枝
        int right = dfs(root->right);
        if (right == -1) return -1;
        return abs(left - right) <= 1 ? max(left, right) + 1 : -1;
    }
};









